#include "cstring"
#include "iostream"

using namespace std;

int _read() {
  static int ans = 0, c;
  static bool p;
  for (c = getchar(); c != '-' && (c < '0' || c > '9'); c = getchar())
    ;
  if (c == '-')
    p = false, c = getchar();
  else
    p = true;
  for (ans = 0; c <= '9' && c >= '0'; c = getchar()) ans = ans * 10 + c - '0';
  return p ? ans : -ans;
}

void _write(int ans) {
  static int a[20], n;
  if (ans == 0) {
    putchar('0');
    return;
  }
  if (ans < 0) {
    putchar('-');
    ans = -ans;
  }
  for (n = 0; ans; ans /= 10) a[n++] = ans % 10;
  for (n--; n >= 0; n--) putchar(a[n] + '0');
  return;
}

int get_max(int *a, int l, int r) {
  static int _m = 0;
  _m = 0;
  for (int i = l; i <= r; i++) _m = max(_m, a[i]);
  return _m;
}

int main() {
  int n, m, t, f[101][101], a[101];
  while (1) {
    n = _read();
    m = _read();
    memset(f, 0x7f7f7f7f, sizeof f);
    if (!n && !m) return 0;
    for (int i = 0; i < n; i++) a[i] = _read();
    for (int i = 0; i < n; i++) f[0][i] = get_max(a, 0, i);
    for (int i = 1; i < m; i++)
      for (int j = i; j < n; j++) {
        for (int k = i - 1; k < j; k++) {
          t = f[i - 1][k] + get_max(a, k + 1, j);
          if (f[i][j] > t) f[i][j] = t;
        }
      }
    _write(f[m - 1][n - 1]);
    putchar('\n');
  }
  return 0;
}
